// Copyright 2022 Tencent
#pragma once
#include "util/noncopyable.h"
#include "base/config.h"
#include "base/function.h"

#include <deque>
#include <tuple>

#include <memory.h>
namespace net_tools::util
{

  template <typename DATAPTR, typename DATAKEY>
  class Bplustreeleaf
  {
  public:
    Bplustreeleaf()
    {
      memset(this, 0, sizeof(Bplustreeleaf));
      level_ = 0;
    };
    ~Bplustreeleaf()
    {
      for (int count = 0; count < size_; ++count)
      {
        delete reinterpret_cast<DATAPTR>(ptr_[count]);
      }
    };
    int level_;
    int size_; //now timevent size
    DATAKEY key_[_C::DEFAULT_BPLUSTREE_SIZE + 1];
    DATAPTR ptr_[_C::DEFAULT_BPLUSTREE_SIZE + 1];
    Bplustreeleaf *next_;
    Bplustreeleaf *before_;
  };

  template <typename DATAPTR, typename DATAKEY>
  class Bplustreenode
  {
  public:
    Bplustreenode(int level)
    {
      memset(this, 0, sizeof(Bplustreenode));
      level_ = level;
    };
    ~Bplustreenode()
    {
      if (level_ == 1)
      {
        for (int count = 0; count < size_; ++count)
        {
          delete reinterpret_cast<Bplustreeleaf<DATAPTR, DATAKEY> *>(ptr_[count]);
        }
      }
      else
      {
        for (int count = 0; count < size_; ++count)
        {
          delete reinterpret_cast<Bplustreenode<DATAPTR, DATAKEY> *>(ptr_[count]);
        }
      }
    };
    int level_;
    int size_;
    DATAKEY key_[_C::DEFAULT_BPLUSTREE_SIZE + 1];
    void *ptr_[_C::DEFAULT_BPLUSTREE_SIZE + 1];
  };

  template <typename DATAPTR, typename DATAKEY>
  class Bplustree : util::noncopyable
  {
    using compare_func = std::function<bool(DATAKEY, DATAKEY, bool)>;

  public:
    using Bplustreeleaf_ = Bplustreeleaf<DATAPTR, DATAKEY>;
    using Bplustreenode_ = Bplustreenode<DATAPTR, DATAKEY>;
    Bplustree(compare_func func);
    ~Bplustree() = default;
    void *Insertdata(DATAPTR dataptr, DATAKEY key, void *beginptr);
    void Del_loop();                                                           //before key include ==
    std::tuple<Bplustreeleaf<DATAPTR, DATAKEY> *, int> Find_leaf(DATAKEY key); //get before key last one index
    DATAKEY Get_cache_min_key() const;
    DATAPTR Get_cache_min_ptr() const;
    Bplustreeleaf<DATAPTR, DATAKEY> *Get_cache_min_leaf();
    bool Is_empty_and_cache();
    Bplustreeleaf<DATAPTR, DATAKEY> *Get_min_leaf();

    void *root_;
    int treelevel_; //tree high, leaf node level
  private:
    // (2,1,true) return true
    // (2,2,true) return true
    // (2,2,false) return false
    compare_func compare_func_;
    void *min_leaf_cache_;
    std::deque<std::pair<void *, int>> Find_cache;
  };

  template <typename DATAPTR, typename DATAKEY>
  Bplustree<DATAPTR, DATAKEY>::Bplustree(compare_func func)
      : root_(new Bplustreenode<DATAPTR, DATAKEY>(1)),
        treelevel_(1),
        compare_func_(std::move(func)),
        Find_cache(){};

  template <typename DATAPTR, typename DATAKEY>
  void *Bplustree<DATAPTR, DATAKEY>::Insertdata(DATAPTR dataptr, DATAKEY key, void *beginptr)
  {
    if (*reinterpret_cast<int *>(beginptr) == 0)
    { //leaf find
      Bplustreeleaf_ *beginptr_ = reinterpret_cast<Bplustreeleaf_ *>(beginptr);
      int begin_ = 0;
      int end_ = beginptr_->size_ - 1;
      if (end_ == -1) [[unlikely]]
      { //don't have data
        beginptr_->key_[0] = key;
        beginptr_->ptr_[0] = dataptr;
        beginptr_->size_++;
        return nullptr;
      }
      if (compare_func_(beginptr_->key_[end_], key, false) && compare_func_(key, beginptr_->key_[begin_], true)) //begin <= key < end_ or size != 1
      {
        int index = 0;
        while (true)
        {
          index = (begin_ + end_) >> 1;
          if (compare_func_(key, beginptr_->key_[index], true)) //key >= index
          {
            begin_ = index;
            if (compare_func_(beginptr_->key_[index + 1], key, false))
            { //key < index+1
              ++index;
              memmove(&beginptr_->key_[index + 1],
                      &beginptr_->key_[index],
                      sizeof(DATAKEY) * (beginptr_->size_ - index));
              memmove(&beginptr_->ptr_[index + 1],
                      &beginptr_->ptr_[index],
                      sizeof(DATAPTR) * (beginptr_->size_ - index));
              beginptr_->ptr_[index] = dataptr;
              beginptr_->key_[index] = key;
              beginptr_->size_++;
              break;
            }
          }
          else
          { //key < index
            end_ = index;
            if (compare_func_(key, beginptr_->key_[index - 1], true))
            { //key >= index-1
              memmove(&beginptr_->key_[index + 1],
                      &beginptr_->key_[index],
                      sizeof(DATAKEY) * (beginptr_->size_ - index));
              memmove(&beginptr_->ptr_[index + 1],
                      &beginptr_->ptr_[index],
                      sizeof(DATAPTR) * (beginptr_->size_ - index));
              beginptr_->ptr_[index] = dataptr;
              beginptr_->key_[index] = key;
              beginptr_->size_++;
              break;
            }
          }
        }
      }
      else
      {                                                      //begin > key or end <= key or size = 1
        if (compare_func_(key, beginptr_->key_[end_], true)) //key >= end or size = 1
        {
          ++end_;
          beginptr_->ptr_[end_] = dataptr;
          beginptr_->key_[end_] = key;
          beginptr_->size_++;
        }
        else
        { //key < begin
          memmove(&beginptr_->key_[begin_ + 1],
                  &beginptr_->key_[begin_],
                  sizeof(DATAKEY) * (beginptr_->size_));
          memmove(&beginptr_->ptr_[begin_ + 1],
                  &beginptr_->ptr_[begin_],
                  sizeof(DATAPTR) * (beginptr_->size_));
          beginptr_->ptr_[begin_] = dataptr;
          beginptr_->key_[begin_] = key;
          beginptr_->size_++;
        }
      }
      if (beginptr_->size_ > _C::DEFAULT_BPLUSTREE_SIZE)
      { // if full return new
        int mid = beginptr_->size_ >> 1;
        Bplustreeleaf_ *ret = new Bplustreeleaf_();
        if (beginptr_->next_)
        {
          beginptr_->next_->before_ = ret;
        }
        ret->next_ = beginptr_->next_;
        beginptr_->next_ = ret;
        ret->before_ = beginptr_;
        memcpy(&ret->key_[0],
               &beginptr_->key_[mid],
               sizeof(DATAKEY) * (beginptr_->size_ - mid));
        memcpy(&ret->ptr_[0],
               &beginptr_->ptr_[mid],
               sizeof(DATAPTR) * (beginptr_->size_ - mid));
        beginptr_->size_ = mid;
        ret->size_ = beginptr_->size_ - mid;
        return ret;
      }
      else
      {
        return nullptr;
      }
    }
    else
    {
      Bplustreenode_ *beginptr_ = reinterpret_cast<Bplustreenode_ *>(beginptr);
      int begin_ = 0;
      int end_ = beginptr_->size_ - 1;
      if (end_ == -1) [[unlikely]]
      { //don't have data
        if (beginptr_->level_ == 1)
        {
          Bplustreeleaf_ *new_ = new Bplustreeleaf_();
          Insertdata(dataptr, key, new_);
          beginptr_->key_[0] = new_->key_[0];
          beginptr_->ptr_[0] = new_;
          beginptr_->size_++;
          return nullptr;
        }
        else
        {
          Bplustreenode_ *new_ = new Bplustreenode_(beginptr_->level_ - 1);
          Insertdata(dataptr, key, new_);
          beginptr_->key_[0] = new_->key_[0];
          beginptr_->ptr_[0] = new_;
          beginptr_->size_++;
          return nullptr;
        }
      }
      void *new_leaf = nullptr;
      if (compare_func_(beginptr_->key_[end_], key, false) && compare_func_(key, beginptr_->key_[begin_], true)) //begin <= key < end_ size != 1
      {
        int index = 0;
        while (true)
        {
          index = ((begin_ + end_) >> 1);                       // 0 + 1 >>1  ->0
          if (compare_func_(key, beginptr_->key_[index], true)) //key >= index
          {
            begin_ = index;
            if (compare_func_(beginptr_->key_[index + 1], key, false))
            { //key < index+1
              if ((new_leaf = Insertdata(dataptr, key, beginptr_->ptr_[index])))
              {
                ++index;
                memmove(&beginptr_->key_[index + 1],
                        &beginptr_->key_[index],
                        sizeof(DATAKEY) * (beginptr_->size_ - index));
                memmove(&beginptr_->ptr_[index + 1],
                        &beginptr_->ptr_[index],
                        sizeof(void *) * (beginptr_->size_ - index));
                beginptr_->key_[index] = reinterpret_cast<Bplustreeleaf_ *>(new_leaf)->key_[0];
                beginptr_->ptr_[index] = new_leaf;
                ++beginptr_->size_;
              }
              break;
            }
          }
          else
          { //key < index
            end_ = index;
            if (compare_func_(key, beginptr_->key_[index - 1], true))
            { //key >= index-1
              if ((new_leaf = Insertdata(dataptr, key, beginptr_->ptr_[index - 1])))
              {
                memmove(&beginptr_->key_[index + 1],
                        &beginptr_->key_[index],
                        sizeof(DATAKEY) * (beginptr_->size_ - index));
                memmove(&beginptr_->ptr_[index + 1],
                        &beginptr_->ptr_[index],
                        sizeof(void *) * (beginptr_->size_ - index));
                beginptr_->key_[index] = reinterpret_cast<Bplustreeleaf_ *>(new_leaf)->key_[0];
                beginptr_->ptr_[index] = new_leaf;
                beginptr_->size_++;
              }
              break;
            }
          }
        }
      }
      else
      {                                                      //begin > key or end <= key or size = 1
        if (compare_func_(key, beginptr_->key_[end_], true)) //key >= end or size = 1
        {
          if ((new_leaf = Insertdata(dataptr, key, beginptr_->ptr_[end_])))
          {
            beginptr_->key_[end_ + 1] = reinterpret_cast<Bplustreeleaf_ *>(new_leaf)->key_[0];
            beginptr_->ptr_[end_ + 1] = new_leaf;
            beginptr_->size_++;
          }
        }
        else
        { //key < begin
          if ((new_leaf = Insertdata(dataptr, key, beginptr_->ptr_[begin_])))
          {
            ++begin_;
            memmove(&beginptr_->key_[begin_ + 1],
                    &beginptr_->key_[begin_],
                    sizeof(DATAKEY) * (beginptr_->size_));
            memmove(&beginptr_->ptr_[begin_ + 1],
                    &beginptr_->ptr_[begin_],
                    sizeof(void *) * (beginptr_->size_));
            beginptr_->key_[begin_ + 1] = reinterpret_cast<Bplustreeleaf_ *>(new_leaf)->key_[0];
            beginptr_->ptr_[begin_ + 1] = new_leaf;
            beginptr_->size_++;
          }
          beginptr_->key_[0] = reinterpret_cast<Bplustreeleaf_ *>(beginptr_->ptr_[0])->key_[0];
        }
      }
      if (beginptr_->size_ > _C::DEFAULT_BPLUSTREE_SIZE)
      { // if full return new
        int mid = beginptr_->size_ >> 1;
        Bplustreenode_ *ret = new Bplustreenode_(beginptr_->level_);
        memcpy(&ret->key_[0],
               &beginptr_->key_[mid],
               sizeof(DATAKEY) * (beginptr_->size_ - mid));
        memcpy(&ret->ptr_[0],
               &beginptr_->ptr_[mid],
               sizeof(void *) * (beginptr_->size_ - mid));
        beginptr_->size_ = mid;
        ret->size_ = beginptr_->size_ - mid;
        if (beginptr_->level_ == treelevel_)
        { //最顶层
          Bplustreenode_ *root = new Bplustreenode_(beginptr_->level_ + 1);
          root->key_[0] = beginptr_->key_[0];
          root->ptr_[0] = beginptr_;
          root->key_[1] = ret->key_[0];
          root->ptr_[1] = ret;
          root_ = root;
          ++treelevel_;
          return nullptr;
        }
        return ret;
      }
      else
      {
        return nullptr;
      }
    }
  };

  template <typename DATAPTR, typename DATAKEY>
  void Bplustree<DATAPTR, DATAKEY>::Del_loop()
  {
    int index = 0;
    bool del = false;
    long unsigned int begin_size = 0;
    begin_size = Find_cache.size();
    bool nothing = false;
    while (!Find_cache.empty())
    {
      index = Find_cache.crbegin()->second;
      if (index == -1 || nothing)
      {
        nothing = true;
        Find_cache.pop_back();
      }
      if (Find_cache.size() == begin_size)
      { //leaf ptr
        Bplustreeleaf_ *begin = reinterpret_cast<Bplustreeleaf_ *>(Find_cache.crbegin()->first);
        begin->before_ = nullptr;
        for (int count = 0; count <= index; count++)
        {
          delete reinterpret_cast<DATAPTR>(begin->ptr_[count]);
        }
        memcpy(&begin->key_[0],
               &begin->key_[index + 1],
               sizeof(DATAKEY) * (begin->size_ - index - 1));
        memcpy(&begin->ptr_[0],
               &begin->ptr_[index + 1],
               sizeof(DATAPTR) * (begin->size_ - index - 1));
        begin->size_ = begin->size_ - index - 1;
        if (begin->size_ == 0)
        {
          del = true;
        }
      }
      else
      {
        index = Find_cache.crbegin()->second;
        Bplustreenode_ *begin = reinterpret_cast<Bplustreenode_ *>(Find_cache.crbegin()->first);
        for (int count = 0; count < index; ++count)
        {
          if (begin->ptr_[count])
          {
            delete reinterpret_cast<Bplustreenode_ *>(begin->ptr_[count]);
          }
        }
        if (del) //下一层一个节点被删除
        {
          del = false;
          if (begin->level_ == 1)
          {
            delete reinterpret_cast<Bplustreeleaf_ *>(begin->ptr_[index]);
          }
          else
          {
            delete reinterpret_cast<Bplustreenode_ *>(begin->ptr_[index]);
          }
          ++index;
          if (index == begin->size_)
          { //该层因为下层删除而清空
            if (Find_cache.size() == 1)
            { //最顶层 空树
              begin->size_ = 0;
              begin->level_ = 1;
              treelevel_ = 1;
              root_ = begin;
            }
            del = true;
          }
        }
        if (!del)
        { //该层没被清空
          memcpy(&begin->key_[0],
                 &begin->key_[index],
                 sizeof(DATAKEY) * (begin->size_ - index));
          memcpy(&begin->ptr_[0],
                 &begin->ptr_[index],
                 sizeof(void *) * (begin->size_ - index));
          begin->key_[0] = reinterpret_cast<Bplustreenode_ *>(begin->ptr_[0])->key_[0];
          begin->size_ = begin->size_ - index;
          if (begin->size_ == 1 && Find_cache.size() == 1 && begin->level_ != 1)
          { //该层只剩一个节点且为最顶层且不为level1 则减小树的大小
            root_ = begin->ptr_[0];
            treelevel_ = reinterpret_cast<Bplustreenode_ *>(root_)->level_;
            begin->size_ = 0; //避免该树清空
            delete begin;     //回收root
          }
        }
      }
      Find_cache.pop_back();
    }
  };
  //must than call del_loop
  template <typename DATAPTR, typename DATAKEY>
  std::tuple<Bplustreeleaf<DATAPTR, DATAKEY> *, int> Bplustree<DATAPTR, DATAKEY>::Find_leaf(DATAKEY key)
  {
    void *beginptr_ = root_;
    // Find_cache should be empty ,can debug here
    for (;;)
    {
      if (*reinterpret_cast<int *>(beginptr_) == 0)
      { //leaf
        Bplustreeleaf_ *beginptr = reinterpret_cast<Bplustreeleaf_ *>(beginptr_);
        int begin_ = 0;
        int end_ = beginptr->size_ - 1;
        if (end_ == -1) [[unlikely]]
        {
          exit(2);
        } //can't be -1, because must have data and timeout to call Find_leaf // debug
        int index = 0;
        if (compare_func_(beginptr->key_[end_], key, false))
        { //key < end_
          while (true)
          {
            index = (begin_ + end_) >> 1;
            if (compare_func_(key, beginptr->key_[index], true))
            { //key >= index
              begin_ = index;
              if (compare_func_(beginptr->key_[index + 1], key, false))
              { //key < index+1
                break;
              }
            }
            else
            { //key < index
              end_ = index;
              if (compare_func_(key, beginptr->key_[index - 1], true))
              { //key >= index-1
                --index;
                break;
              }
            }
          }
        }
        else
        { // end <= key or size = 1
          if (end_ == 0)
          {
            if (compare_func_(key, beginptr->key_[end_], true))
            { // key >= end
              index = end_;
            }
            else
            {
              index = -1;
            }
          }
          else
          {
            index = end_;
          }
        }
        Find_cache.push_back(std::make_pair(beginptr, index));
        return std::make_tuple(beginptr, index);
      }
      else
      {
        Bplustreenode_ *beginptr = reinterpret_cast<Bplustreenode_ *>(beginptr_);
        int begin_ = 0;
        int end_ = beginptr->size_ - 1;
        int index = 0;
        if (compare_func_(beginptr->key_[end_], key, false))
        { //key < end_
          while (true)
          {
            index = (begin_ + end_) >> 1;
            if (compare_func_(key, beginptr->key_[index], true))
            { //key >= index
              begin_ = index;
              if (compare_func_(beginptr->key_[index + 1], key, false))
              { //key < index+1
                break;
              }
            }
            else
            { //key < index
              end_ = index;
              if (compare_func_(key, beginptr->key_[index - 1], true))
              { //key >= index-1
                --index;
                break;
              }
            }
          }
        }
        else
        { //end <= key or size = 1
          if (end_ == 0)
          {
            if (compare_func_(key, beginptr->key_[end_], true))
            { // key >= end
              index = end_;
            }
            else
            {
              index = -1;
            }
          }
          else
          {
            index = end_;
          }
        }
        if (index == -1)
        {
          for (int level = *reinterpret_cast<int *>(beginptr_); level > 0; --level)
          {
            Find_cache.push_back(std::make_pair(beginptr, 0));
            beginptr_ = reinterpret_cast<void *>(beginptr->ptr_[0]);
          }
          Find_cache.push_back(std::make_pair(beginptr, -1));
          Bplustreeleaf_ *beginptr = reinterpret_cast<Bplustreeleaf_ *>(beginptr_);
          return std::make_tuple(beginptr, -1);
        }
        else
        {
          Find_cache.push_back(std::make_pair(beginptr, index));
          beginptr_ = reinterpret_cast<void *>(beginptr->ptr_[index]);
        }
      }
    }
  };

  template <typename DATAPTR, typename DATAKEY>
  DATAKEY Bplustree<DATAPTR, DATAKEY>::Get_cache_min_key() const
  {
    return reinterpret_cast<Bplustreeleaf_ *>(min_leaf_cache_)->key_[0];
  };

  template <typename DATAPTR, typename DATAKEY>
  DATAPTR Bplustree<DATAPTR, DATAKEY>::Get_cache_min_ptr() const
  {
    return reinterpret_cast<Bplustreeleaf_ *>(min_leaf_cache_)->ptr_[0];
  };

  template <typename DATAPTR, typename DATAKEY>
  Bplustreeleaf<DATAPTR, DATAKEY> *Bplustree<DATAPTR, DATAKEY>::Get_min_leaf()
  {
    Bplustreenode_ *begin = reinterpret_cast<Bplustreenode_ *>(root_);
    for (;;)
    {
      if (*reinterpret_cast<int *>(begin) == 0)
      {
        Bplustreeleaf_ *end = reinterpret_cast<Bplustreeleaf_ *>(begin);
        if (end->size_ == 0) [[unlikely]]
        {
          return nullptr;
        }
        else
        {
          return end;
        }
      }
      if (begin->size_)
      {
        begin = reinterpret_cast<Bplustreenode_ *>(begin->ptr_[0]);
      }
      else
      {
        return nullptr;
      }
    }
  };

  template <typename DATAPTR, typename DATAKEY>
  bool Bplustree<DATAPTR, DATAKEY>::Is_empty_and_cache()
  {
    Bplustreenode_ *ret = reinterpret_cast<Bplustreenode_ *>(Get_min_leaf());
    if (ret)
    {
      min_leaf_cache_ = ret;
      return false;
    }
    else
    {
      min_leaf_cache_ = nullptr;
      return true;
    }
  };

} // namespace net_tools::util